package bin_tree_order;

import java.util.*;

public class Main {
    static int index = 0; // 控制遍历字符串

    public static class TreeNode {
        public TreeNode left;
        public TreeNode right;
        public Character val;

        public TreeNode (Character val) {
            this.val = val;
        }
    }

    public static void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s = sc.next();
            TreeNode root = getTree(s);
            inOrder(root);
            index = 0;
            System.out.println();
        }
    }

    public static TreeNode getTree(String s) {
        if (index == s.length() || s.charAt(index) == '#') {
            return null;
        }
        TreeNode root = new TreeNode(s.charAt(index));
        System.out.println(root.val);
        index ++;
        root.left = getTree(s);
        index ++;
        root.right = getTree(s);
        return root;

    }
}
